﻿using System;

namespace AlgorithmPractice;

/// <summary>
/// 希尔排序
/// </summary>
public class ShellsSort
{
    public static void Sort(int[] toBeSort)
    {
        StartSort(toBeSort);
        Console.WriteLine(string.Join("、", toBeSort));
    }

    /// <summary>
    /// 希尔排序是将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；
    /// 然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
    /// </summary>
    /// <param name="toBeSort"></param>
    private static void StartSort(int[] toBeSort)
    {
        var len = toBeSort.Length;
        int i, j;
        
        for (var step = len / 2; step >= 1; step /= 2)
        {
            // 直接插入排序
            for (i = step; i < len; i++)
            {
                var temp = toBeSort[i];
                
                for (j = i - step; j >= 0 && toBeSort[j] > temp; j -= step)
                {
                    toBeSort[j + step] = toBeSort[j];
                }

                toBeSort[j + step] = temp;
            }
        }
    }
}